package com.arron.algorithm.leetcodetop100.回溯;

import java.util.*;

public class 电话号码的字母组合 {


    Map<String, String> phoneNumberMap;
    List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {

        if (digits == null || digits.length() == 0) {
            return res;
        }


        phoneNumberMap = new HashMap<>();

        //初始化
        phoneNumberMap.put("2", "abc");
        phoneNumberMap.put("3", "def");
        phoneNumberMap.put("4", "ghi");
        phoneNumberMap.put("5", "jkl");
        phoneNumberMap.put("6", "mno");
        phoneNumberMap.put("7", "pqrs");
        phoneNumberMap.put("8", "tuv");
        phoneNumberMap.put("9", "wxyz");


        if (digits.length() == 1) {
            String s = phoneNumberMap.get(digits);

            for (int i = 0; i < s.length(); i++) {
                res.add(s.charAt(i) + "");
            }
            return res;
        }


        char[] chars = digits.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            dfs(chars[i]+"", chars,i, new StringBuffer());
        }


        return res;
    }

    private void dfs(String number, char[] digits ,int numberStart, StringBuffer sb) {

        if (numberStart >= phoneNumberMap.size()) {
            return;
        }

        String curLetter = phoneNumberMap.get(number);

        char[] chars = curLetter.toCharArray();

        for (int j = 0; j < chars.length; j++) {
            sb.append(chars[j]);
            if (sb.length() == digits.length) res.add(sb.toString());
            numberStart++;
            if (numberStart >= digits.length) {
                numberStart--;
                sb.deleteCharAt(sb.length() - 1);
                continue;
            }
            dfs(digits[numberStart]+"",digits, numberStart, sb);
            numberStart--;
            sb.deleteCharAt(sb.length() - 1);

        }

    }

    public static void main(String[] args) {
        电话号码的字母组合 letterCombinations = new 电话号码的字母组合();
        List<String> strings = letterCombinations.letterCombinations("23");

        System.out.println(strings);
    }

}
